{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Ch `06`: Concept `01`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Hidden Markov model forward algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Oof this code's a bit complicated if you don't already know how HMMs work. Please see the book chapter for step-by-step explanations. I'll try to improve the documentation, or feel free to send a pull request with your own documentation!\n",
    "\n",
    "First, let's import TensorFlow and NumPy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import tensorflow as tf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Define the HMM model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "class HMM(object):\n",
    "    def __init__(self, initial_prob, trans_prob, obs_prob):\n",
    "        self.N = np.size(initial_prob)\n",
    "        self.initial_prob = initial_prob\n",
    "        self.trans_prob = trans_prob\n",
    "        self.emission = tf.constant(obs_prob)\n",
    "\n",
    "        assert self.initial_prob.shape == (self.N, 1)\n",
    "        assert self.trans_prob.shape == (self.N, self.N)\n",
    "        assert obs_prob.shape[0] == self.N\n",
    "\n",
    "        self.obs_idx = tf.placeholder(tf.int32)\n",
    "        self.fwd = tf.placeholder(tf.float64)\n",
    "\n",
    "    def get_emission(self, obs_idx):\n",
    "        slice_location = [0, obs_idx]\n",
    "        num_rows = tf.shape(self.emission)[0]\n",
    "        slice_shape = [num_rows, 1]\n",
    "        return tf.slice(self.emission, slice_location, slice_shape)\n",
    "\n",
    "    def forward_init_op(self):\n",
    "        obs_prob = self.get_emission(self.obs_idx)\n",
    "        fwd = tf.multiply(self.initial_prob, obs_prob)\n",
    "        return fwd\n",
    "\n",
    "    def forward_op(self):\n",
    "        transitions = tf.matmul(self.fwd, tf.transpose(self.get_emission(self.obs_idx)))\n",
    "        weighted_transitions = transitions * self.trans_prob\n",
    "        fwd = tf.reduce_sum(weighted_transitions, 0)\n",
    "        return tf.reshape(fwd, tf.shape(self.fwd))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Define the forward algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def forward_algorithm(sess, hmm, observations):\n",
    "    fwd = sess.run(hmm.forward_init_op(), feed_dict={hmm.obs_idx: observations[0]})\n",
    "    for t in range(1, len(observations)):\n",
    "        fwd = sess.run(hmm.forward_op(), feed_dict={hmm.obs_idx: observations[t], hmm.fwd: fwd})\n",
    "    prob = sess.run(tf.reduce_sum(fwd))\n",
    "    return prob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Let's try it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Probability of observing [0, 1, 1, 2, 1] is 0.004540300799999999\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    initial_prob = np.array([[0.6], [0.4]])\n",
    "    trans_prob = np.array([[0.7, 0.3], [0.4, 0.6]])\n",
    "    obs_prob = np.array([[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]])\n",
    "\n",
    "    hmm = HMM(initial_prob=initial_prob, trans_prob=trans_prob, obs_prob=obs_prob)\n",
    "\n",
    "    observations = [0, 1, 1, 2, 1]\n",
    "    with tf.Session() as sess:\n",
    "        prob = forward_algorithm(sess, hmm, observations)\n",
    "        print('Probability of observing {} is {}'.format(observations, prob))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
